package com.example.lcode.greedy;

/**
 * @version 1.0
 * @author: ChuJie_Lin
 * @since: 2021-09-23 12:32
 **/
public class Question673 {

    public int findNumberOfLIS(int[] nums) {
        int num = 0;
        int maxLength = 0;
        int []dp = new int[nums.length];
        int []cnt = new int[nums.length];
        // init
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
            cnt[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] = cnt[i] + cnt[j];
                    }
                }
            }
            if (dp[i] > maxLength) {
                maxLength = dp[i];
                num = cnt[i];
            } else if (dp[i] == maxLength) {
                num += cnt[i];
            }
        }
        return num;
    }

}
